package twobranchTree.buildTreeOne;
/**
 * @Date 2020/02/25
 * @author 王光浩
 * @Thinking 使用递归的方法进行。通过中序遍历结果辅助后续遍历结果，来自上而下的还原整颗数。（这里需要使用视图）
 * @Analys 时间复杂度O（n^2），空间复杂度O（）
 */



import twobranchTree.preorderTraversal.TreeNode;

public class MyMethodOne {
	private int[] copyInorder;
	private int[] copyPost;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    	this.copyInorder=inorder;
    	this.copyPost=postorder;
    	if(inorder.length==0)return null;
    	TreeNode root=new TreeNode(postorder[postorder.length-1]);
    	recursively(0,inorder.length-1,0,postorder.length-1,root);
    	return root;
    }
    //构建根节点为root的树（补全它的左右节点信息）
	private void recursively(int inorderLeft,int inorderRight,int postLeft,int postRight,TreeNode root) {
		if((inorderRight-inorderLeft)<1)return;  //该节点为叶子节点
		int inorderIndex=-1;
		for(int i=inorderLeft;i<=inorderRight;i++) {  //找到root在中序中的位置（找到中序中的左右子树，范围）
			if(copyInorder[i]==copyPost[postRight]) {
				inorderIndex=i;
				break;
			}				
		}
		if(inorderIndex==inorderLeft) {   //左子树为空
			//将root与右节点相连接
			TreeNode tem=new TreeNode(copyPost[postRight-1]);
			root.right=tem;
			//进入右子树，向下继续递归
			recursively(inorderIndex+1,inorderRight,postLeft,postRight-1,tem);
		}
		else if(inorderIndex==inorderRight) {  //右子树为空
			//将root与左节点相连接
			TreeNode tem=new TreeNode(copyPost[postRight-1]);
			root.left=tem;
			//进入左子树，继续递归
			recursively(inorderLeft,inorderIndex-1,postLeft,postRight-1,tem);
		}
		else {   //左右子树都不为空
			int postPosition=postLeft+inorderIndex-inorderLeft-1;    //找到后序中左子树最后一个节点位置
			//将左右节点进行连接
			TreeNode tem1=new TreeNode(copyPost[postPosition]);
			root.left=tem1;
			TreeNode tem2=new TreeNode(copyPost[postRight-1]);
			root.right=tem2;
			//进入左子树
			recursively(inorderLeft,inorderIndex-1,postLeft,postPosition,tem1);
			//进入右子树
			recursively(inorderIndex+1,inorderRight,postPosition+1,postRight-1,tem2);
		}
	}
}
